package com.wcj.sort;

public class 快速排序 {

    public static void main(String[] args) {
        int[] arr = new int[]{23,12,36,451,2,89,78,54};
        QuickSort(arr,0,arr.length - 1);
        for (int i : arr) {
            System.out.println(i);
        }
    }

    public static void quickSort(int[] arr){
        quickSort(arr,0,arr.length - 1);
    }

    public static void quickSort(int[] arr,int left,int right){
            if (left < right){
                int pivot = median(arr,left,right);
                int i = left;
                int j = right;
                while (true){
                    while (arr[++i] < pivot){

                    }
                    while (arr[--j] > pivot){

                    }
                    if (i < j)
                        swap(arr,i,j);
                    else
                        break;
                }
                quickSort(arr,left,i-1);
                quickSort(arr,i+1,right);
            }


    }

    public static int median(int[] arr,int left,int right){
        int center = left + (right-left)/2;
        if (arr[center] < arr[left]){
            swap(arr,left,center);
        }
        if (arr[right] < arr[left]){
            swap(arr,left,right);
        }
        if (arr[right] < arr[center]){
            swap(arr,center,right);
        }
        return arr[center];
    }

    public static void swap(int[] arr,int position,int position2){
        int tmp = arr[position];
        arr[position] = arr[position2];
        arr[position2] = tmp;
    }

    public static void QuickSort(int a[],int low,int high){
        int pivot;
        if (high > low){
            pivot = Partition(a,low,high);
            QuickSort(a,low,pivot - 1);
            QuickSort(a,pivot + 1,high);
        }
    }

    private static int Partition(int[] a, int low, int high) {
        int left = low;
        int right = high;
        int pivot_item = a[low];
        while (left < right){
            while (a[left] <= pivot_item){
                left++;
            }
            while (a[right] > pivot_item){
                right--;
            }
            if (left < right){
                swap(a, left, right);
            }
        }
        a[low] = a[right];
        a[right] = pivot_item;
        return right;
    }
}
